package com.qjc.demo.algorithm;

import java.util.Arrays;

/**
 * @ClassName: MaxProduct
 * @Description: 整形数组nums，在数组中找出由三个数字组成的最大乘积，并输出这个乘积。乘积不会越界
 * 考察重点：线性扫描
 * @Author: qjc
 * @Date: 2022/5/5 5:30 PM
 */
public class MaxProduct {

    // 利用排序来求最大的乘积，时间复杂度O(nlog n)
    public static int sort(int[] nums) {
        // 升序排列
        Arrays.sort(nums);
        int n = nums.length;
        // nums[0] * nums[1] * nums[n - 1] 如果有负数，则最小的两个数相乘，然后再乘上最大的一个数
        // nums[n - 1] * nums[n - 2] * nums[n - 3] 如果灭有负数，则直接让最大的三个数相乘即可
        return Math.max(nums[0] * nums[1] * nums[n - 1], nums[n - 1] * nums[n - 2] * nums[n - 3]);
    }

    // 利用线性扫描来求最大的乘积，时间复杂度O(n)
    public static int getMaxMin(int[] nums) {
        // 定义最小值和次小值
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        // 定义最大值，次大值，第三大值
        int max1 = Integer.MIN_VALUE, max2 = Integer.MIN_VALUE, max3 = Integer.MIN_VALUE;
        for (int num : nums) {
            if (num < min1) {
                // 如果小于最小值，那么min1赋值给min2，最小值num赋值给min1
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                // 如果num小于次小值，那么把num赋值给次小值
                min2 = num;
            }
            if (num > max1) {
                // 如果num大于最大值，那么max2赋值给第三大值max3，max1赋值给次大值max2，num赋值给最大值max1
                max3 = max2;
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                // 如果num大于次大值，那么max2赋值给第三大值max3，num赋值给次大值max2
                max3 = max2;
                max2 = num;
            } else if (num > max3) {
                // 如果num大于第三大值，那么num赋值给第三大值
                max3 = num;
            }
        }
        return Math.max(min1 * min2 * max1, max1 * max2 * max3);
    }

    public static void main(String[] args) {
        System.out.println(sort(new int[]{1, 2, 3, 4, 5, 6}));
        System.out.println(getMaxMin(new int[]{1, 2, 3, 4, 5, 6}));
    }

}
